The discrete Fourier transform (DFT) plays a key role in digital signal processing in areas such as spectral analysis, frequency-domain filtering, and polyphase transformations. Several efficient algorithms for computing the DFT have been proposed over the years. Indeed, the existence of such fast algorithms has made the DFT the workhorse of digital signal processing.
For each algorithm, one of several architectures may be chosen, depending on the given requirements (e.g., speed, cost, and power). For real-time, very high-speed signal processing, a dedicated special-purpose hardware processor is often required. An efficient pipeline architecture that implements the Cooley-Tukey fast Fourier transform (FFT) algorithm has been proposed and has received considerable attention. Interest is particularly great for spaceborne applications, such as satellite communications, where efficient implementations are of paramount importance because of power and size constraints.
The need for performing various size FFTs arises when digitally demultiplexing a number of frequency-multiplexed carriers that occupy bandwidths of various sizes, using a frequency-domain approach. An FFT is first performed on the digital samples of the composite signal. This is followed by multiplication of the resulting frequency coefficients across the overall spectrum by any desired filter functions to separate the various carriers and introduce spectral shaping, if desired. IFFTs are then performed on the individual carriers to recover the time domain waveforms. To minimize the amount of computation involved, the IFFT performed on a given carrier should only cover the frequency band occupied by that carrier. Thus, different carrier bandwidths will result in different IFFT sizes.
Multiple FFT sizes are also needed for multiple resolution spectral analysis and polyphase transformations on carriers of unequal size.
An old method of performing FFTs of various sizes dedicated a different processor to each size of FFT to be performed. Pipeline processors are often used when real time, high speed processing is desired. Therefore, in order to perform the different-size FFTs, several FFT pipelines were needed. The number of stages in each pipeline would be determined by the size of the FFT to be performed by the particular pipeline.
For each FFT pipeline, the sequence of the delays in the pipeline was strictly increasing or strictly decreasing.
However, the old pipeline method required a large amount of hardware to perform all the desired transforms which was disadvantageous. For example, if 3 different FFT sizes were required, 3 pipelines, each with a number of stages matched to one of the desired FFTs would be required.
Another disadvantage of the old method is that a failure in one of the delay elements could cause the entire pipeline processor to fail and consequently, the system was unable to perform more transforms having that particular size (assuming there was only one pipeline for each size transform).